import copy
# 初始状态和目标状态
initial = [
    [2, 8, 3],
    [1, 6, 4],
    [7, 0, 5]
]
goal = [
    [1, 2, 3],
    [8, 0, 4],
    [7, 6, 5]
]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def find_0(state):  # 返回0即空格的位置
    for i in state:
        for j in i:
            if j == 0:
                return state.index(i), i.index(j)

def print_state(state): # 可视化输出
    for i in state:
        print(i)

def print_path(Close):
    path = []
    tmp = Close[-1]
    while tmp[2] != -1:
        path.append(Close[tmp[2]][0])
        tmp = Close[tmp[2]]
    path.reverse()
    print(f'BFS 求解八数码如下: ')
    for i in path:
        print_state(i)
        print('↓')
    print_state(initial)
    print(f'长度为 {len(path)}, 总试探步数 {len(Close) - 1}')


def BFS():
    Open = [(initial, 0, -1)]  # 三元组: 状态、当前结点下标、父节点下标
    Close = []
    visited = []
    while Open:
        cur = Open.pop(0)
        Close.append(cur)
        visited.append(cur[0])
        if cur[0] == goal:
            print_path(Close)
            return
        cx, cy = find_0(cur[0])
        for dir in dirs:
            tx = cx + dir[0]
            ty = cy + dir[1]
            tmp = cur[0].copy()  # 需要浅拷贝!
            if 0 <= tx < 3 and 0 <= ty < 3:  # 移动后是否出界
                tmp[tx][ty], tmp[cx][cy] = tmp[cx][cy], tmp[tx][ty]  # 与0交换位置，得到新的状态
                if tmp not in visited:  # 移动后的状态是否扩展过
                    visited.append(tmp)
                    Open.append((tmp, len(Close), cur[1]))



